package JZ_Offer.dataStructure.list;

import base.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 两个链表的第一个公共结点
 * <p>
 * 输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
 * <p>
 * 例如，输入{1,2,3,6,7},{4,5,6,7}时，两个无环的单向链表的结构如下图所示：可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
 */
public class JZ52_两个链表的第一个公共结点 {

    public static void main(String[] args) {
        ListNode c = new ListNode(8);
        ListNode d = new ListNode(10);
        // ListNode e = new ListNode(5);
        c.next = d;
        // d.next = e;

        ListNode headA = new ListNode(1);
        ListNode b = new ListNode(2);
        headA.next = b;
        b.next = c;

        ListNode headB = new ListNode(0);
        ListNode bb = new ListNode(3);
        ListNode bc = new ListNode(4);
        headB.next = bb;
        bb.next = bc;
        // bc.next = c;

        ListNode listNode = FindFirstCommonNode1(headA, headB);
        System.out.println(listNode);
    }

    public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }

        Set<ListNode> set = new HashSet<>();

        while (pHead1 != null || pHead2 != null) {
            if (pHead1 != null) {
                ListNode next1 = pHead1.next;
                boolean b = set.add(pHead1);
                if (!b) {
                    return pHead1;
                }
                pHead1 = next1;
            }

            if (pHead2 != null) {
                ListNode next2 = pHead2.next;
                boolean b = set.add(pHead2);
                if (!b) {
                    return pHead2;
                }
                pHead2 = next2;
            }
        }
        return null;
    }

    /**
     * 链接：https://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46?answerType=1&f=discussion
     * 来源：牛客网
     * <p>
     * 按照自己以往的思路肯定第一反应用HashSet和HashMap就能很快解决此问题，但是如果真的面试出了这道题目肯定不是面试官想要的思路。
     * 有一种简单的解调思路：那就是遍历两遍这两个链表，如果有重复的节点，那么一定能够使遍历的指针相等。
     * 关键点: 如何让两个链表同时到达相交节点,两个链表长度不一致,我么让A遍历后遍历B,B遍历后遍历A,这样两个链表长度就相等了,
     * 主要是结束条件:判断条件当两个节点相等时候就结束了,如果相交,第二次遍历肯定能够同时到达相交节点,如果不想交,第二次遍历后,同时到达尾结点,同时为null,条件不命中结束,返回null
     */
    public static ListNode FindFirstCommonNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            if (p1 == null) p1 = headB;
            else p1 = p1.next;
            if (p2 == null) p2 = headA;
            else p2 = p2.next;
        }
        return p1;
    }

}
